#ifndef COMPILER_CFG_H
#define COMPILER_CFG_H

#include "IntermediateCode.h"
#include "IntSet.h"

namespace Compiler
{
	namespace Intermediate
	{
		using namespace CoreLib::Basic;

		class ControlFlowNode
		{
		public:
			int Id;
			List<ControlFlowNode*> Entries;
			ControlFlowNode* Exits[2];
			LinkedList<Instruction> Code;
		public:
			ControlFlowNode * ImmediateDominator, * ReverseImmediateDominator;
			List<ControlFlowNode *> DomChildren, ReverseDomChildren;
			List<ControlFlowNode *> DominateFrontier, ReverseDominateFrontier;
			IntSet LiveOut, LiveIn;
		public:
			ControlFlowNode()
			{
				Id = -1;
				Exits[0] = 0;
				Exits[1] = 0;
				ImmediateDominator = 0;
				ReverseImmediateDominator = 0;
			}
			ControlFlowNode(ControlFlowNode && node)
			{
				operator=(_Move(node));
			}
			ControlFlowNode & operator = (ControlFlowNode && node)
			{
				Id = node.Id;
				Entries = _Move(node.Entries);
				Exits[0] = node.Exits[0]; Exits[1] = node.Exits[1];
				Code = _Move(node.Code);
				return *this;
			}
			InstructionNode * FirstInstruction()
			{
				InstructionNode * rs = Code.FirstNode();
				while (rs && rs->Value.Func == Operation::Phi)
					rs = rs->GetNext();
				return rs;
			}
			int GetExitCount() const
			{
				if (Exits[0] == 0)
					return 0;
				else if (Exits[1] == 0)
					return 1;
				else
					return 2;
			}
		};

		class ControlFlowGraph
		{
		private:
			void BuildDominatorTree();
			void ComputeDominateFrontier();
			void BuildReverseDominatorTree();
			void ComputeReverseDominateFrontier();
			
			static void AddEdge(ControlFlowNode * node1, int outId, ControlFlowNode * node2);
		public:
			ControlFlowNode *Source, *Sink;
			List<RefPtr<ControlFlowNode>> Nodes;
			List<RefPtr<Variable>> Variables;
			int ParameterCount, VariableSize;
			List<InstructionNode *> VarDefs;
			List<ControlFlowNode *> GetPostOrder();
			List<ControlFlowNode *> GetPostOrderOnReverseCFG();
			ControlFlowGraph()
			{}
			ControlFlowGraph(const ControlFlowGraph & graph)
			{
				Variables = graph.Variables;
				VarDefs = graph.VarDefs;
				ParameterCount = graph.ParameterCount;
				VariableSize = graph.VariableSize;
				Nodes = graph.Nodes;
				Source = graph.Source;
				Sink = graph.Sink;
				
			}
			ControlFlowGraph(ControlFlowGraph && graph)
			{
				Variables = _Move(graph.Variables);
				VarDefs = _Move(graph.VarDefs);
				ParameterCount = graph.ParameterCount;
				VariableSize = graph.VariableSize;
				Nodes = _Move(graph.Nodes);
				Source = graph.Source;
				Sink = graph.Sink;
			}
			ControlFlowNode * AddNode()
			{
				Nodes.Add(new ControlFlowNode());
				Nodes.Last()->Id = Nodes.Count()-1;
				return Nodes.Last().Ptr();
			}
			void Dump(const String & fileName);
			void ConvertToSSA();
			void ComputeDominatorTree();
			void ComputeVariableLiveness();
			static ControlFlowGraph * FromCode(const Function & code);
			void ToCode(Function & func);
		};
	}
}

#endif